// https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

// 题干：给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
//      （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

// 示例：输入：root = [3,9,20,null,null,15,7]
//      输出：[[3],[20,9],[15,7]]

// 碎语：层序遍历的翻版，牢固掌握了层序遍历的情况下，就会很轻松
//       让偶数行的信息逆序即可

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution
{
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root)
    {
       vector<vector<int>> ret;
       queue<TreeNode*> q;

       // 特殊情况处理
       if (root == nullptr) return ret;

       // 如果不是，我们把根节点入队，并且定义一个布尔变量
       q.push(root);
       bool flag = true; // true表示奇数行，不用逆序；false表示偶数行，需要逆序

       while (q.size()){ // 如果当前层存在结点
           int sz = q.size(); // 保存当前层结点个数
           vector<int> tmp;

           for (int i = 0 ; i < sz ; i++){ // 遍历当前层所有结点
               TreeNode* t = q.front();
               q.pop(); // 弹出自己
               tmp.push_back(t->val); // 留下其值

               // 子节点入队
               if (t->left) q.push(t->left);
               if (t->right) q.push(t->right);
           }

           // 处理当前层
           if (flag){
               flag = false;
               ret.push_back(tmp);
           }
           else {
               flag = true;
               reverse(tmp.begin(), tmp.end());
               ret.push_back(tmp);
           }
       }

       return ret;
    }
};

int main()
{
    Solution sol;

    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    vector<vector<int>> index = sol.zigzagLevelOrder(root);
    for (const auto& vec : index){
        for (const auto& num : vec){
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}